//class Solution {
//public:
//    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//        _hanota(A, B, C, A.size());
//    }
//
//    void _hanota(vector<int>& A, vector<int>& B, vector<int>& C, int size)
//    {
//        if (size == 0) return;
//        _hanota(A, C, B, size - 1);
//        C.push_back(A.back());
//        A.pop_back();
//        _hanota(B, A, C, size - 1);
//    }
//};



//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        if (list1 == nullptr || list2 == nullptr) return (list1 == nullptr) ? list2 : list1;
//        if (list1->val > list2->val)
//        {
//            list2->next = mergeTwoLists(list1, list2->next);
//            return list2;
//        }
//        else
//        {
//            list1->next = mergeTwoLists(list2, list1->next);
//            return list1;
//        }
//    }
//};



//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        if (head == nullptr || head->next == nullptr) return head;
//        ListNode* newhead = reverseList(head->next);
//        head->next->next = head;
//        head->next = nullptr;
//        return newhead;
//    }
//};



//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (head == nullptr || head->next == nullptr) return head;
//        ListNode* tmp = swapPairs(head->next->next);
//        ListNode* newhead = head->next;
//        newhead->next = head;
//        head->next = tmp;
//        return newhead;
//    }
//};




//class Solution {
//public:
//    double myPow(double x, int n) {
//        return (n < 0) ? (1.0 / Pow(x, -(long long)n)) : Pow(x, n);
//    }
//
//    double Pow(double x, long long n)
//    {
//        if (n == 0) return 1.0;
//        double tmp = Pow(x, n / 2);
//        return (n % 2) ? (tmp * tmp * x) : (tmp * tmp);
//    }
//};



class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if (root->left == nullptr && root->right == nullptr) return (root->val == 1) ? true : false;
        bool leftVal = evaluateTree(root->left);
        bool rightVal = evaluateTree(root->right);
        return (root->val == 2) ? (leftVal | rightVal) : (leftVal & rightVal);
    }
};